package com.zyk.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangsan
 * @date 2021/4/18 13:19
 */
public class C116 {
    public Node connect(Node root) {
        if(root == null) return null;
        Queue<Node> q = new LinkedList<>(){{ add(root); }};
        Node end = root, nextEnd = null, cur;
        while (!q.isEmpty()) {
            cur = q.poll();
            if(cur.left != null) {
                q.add(cur.left);
                nextEnd = cur.left;
            }
            if(cur.right != null) {
                q.add(cur.right);
                nextEnd = cur.right;
            }
            if(cur == end)
                end = nextEnd;
            else
                cur.next = q.peek();
        }
        return root;
    }

    // 两种情况:
    // 1:  node.left.next = node.right
    // 2:  node.right.next = node.right.next = node.next.left
    public Node connect2(Node root) {
        if (root == null) {
            return root;
        }
        // 从根节点开始
        Node leftmost = root;
        while (leftmost.left != null) {
            // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
            Node head = leftmost;
            while (head != null) {
                // CONNECTION 1
                head.left.next = head.right;
                // CONNECTION 2
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                // 指针向后移动
                head = head.next;
            }
            // 去下一层的最左的节点
            leftmost = leftmost.left;
        }
        return root;
    }




    // for test
    public static void main(String[] args) {
        Queue<Object> q = new LinkedList<>();
        System.out.println(q.peek());
    }
}


class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
